package pers.lls.hds.map;


/**
 * 广度优先搜索
 *
 * @author lilichai
 */
public class BfsGraph {
    private final int MAX_VERTS = 20;
    private BfsVertex BfsVertexList[];
    private int adjMat[][];
    private int nVerts;
    private Queue theQueue;

    public BfsGraph() {
        BfsVertexList = new BfsVertex[MAX_VERTS];

        adjMat = new int[MAX_VERTS][MAX_VERTS];
        nVerts = 0;
        for (int j = 0; j < MAX_VERTS; j++)
            for (int k = 0; k < MAX_VERTS; k++)
                adjMat[j][k] = 0;
        theQueue = new Queue();
    }

    public void addBfsVertex(char lab) {
        BfsVertexList[nVerts++] = new BfsVertex(lab);
    }

    public void addEdge(int start, int end) {
        adjMat[start][end] = 1;
        adjMat[end][start] = 1;
    }

    public void displayBfsVertex(int v) {
        System.out.print(BfsVertexList[v].label);
    }

    public void bfs() {
        BfsVertexList[0].wasVisited = true;
        displayBfsVertex(0);
        theQueue.insert(0);
        int v2;

        while (!theQueue.isEmpty()) {
            int v1 = theQueue.remove();

            while ((v2 = getAdjUnvisitedBfsVertex(v1)) != -1) {
                BfsVertexList[v2].wasVisited = true;
                displayBfsVertex(v2);
                theQueue.insert(v2);
            }
        }

        for (int j = 0; j < nVerts; j++)
            BfsVertexList[j].wasVisited = false;
    }

    public int getAdjUnvisitedBfsVertex(int v) {
        for (int j = 0; j < nVerts; j++)
            if (adjMat[v][j] == 1 && BfsVertexList[j].wasVisited == false)
                return j;
        return -1;
    }

    public static void main(String[] args) {
        BfsGraph theBfsGraph = new BfsGraph();
        theBfsGraph.addBfsVertex('A');
        theBfsGraph.addBfsVertex('B');
        theBfsGraph.addBfsVertex('C');
        theBfsGraph.addBfsVertex('D');
        theBfsGraph.addBfsVertex('E');

        theBfsGraph.addEdge(0, 1);
        theBfsGraph.addEdge(1, 2);
        theBfsGraph.addEdge(0, 3);
        theBfsGraph.addEdge(3, 4);

        System.out.print("Visits: ");
        theBfsGraph.bfs();
        System.out.println();
    }


}

class Queue {
    private final int SIZE = 20;
    private int[] queArray;
    private int front;
    private int rear;

    public Queue() {
        queArray = new int[SIZE];
        front = 0;
        rear = -1;
    }

    public void insert(int j) {
        if (rear == SIZE - 1)
            rear = -1;
        queArray[++rear] = j;
    }

    public int remove() {
        int temp = queArray[front++];
        if (front == SIZE)
            front = 0;
        return temp;
    }

    public boolean isEmpty() {
        return (rear + 1 == front || (front + SIZE - 1 == rear));
    }

}

class BfsVertex {
    public char label;
    public boolean wasVisited;

    public BfsVertex(char lab) {
        label = lab;
        wasVisited = false;
    }

}


